package leetcode.Fiftyone_to_One_hundred;

import java.util.Arrays;

/**
 * 颜色分类【荷兰国旗问题】
 * 可以使用的算法：
 * 1. 一般的排序算法
 * 2. 计数排序：因为只存在012三个数字，统计他们的个数，然后按顺序放回原数组即可
 * 3. 三路快排
 */
public class Test75 {

//    public static void sortColors(int[] nums) {
//        int[] count = new int[3];
//        for (int i = 0; i < nums.length; i++) {
//            count[nums[i]]++;
//        }
//        int index = 0;
//        for (int j = 0; j < 3; j++) {
//            for (int i = 0; i < count[j]; i++) {
//                nums[index++] = j;
//            }
//        }
//    }
//
//    public static void sortColors2(int[] nums) {
//        int h = 1;
//        while (h < nums.length / 3) {
//            h = h * 3 + 1;
//        }
//        while (h >= 1) {
//            for (int i = h; i < nums.length; i++) {
//                for (int j = i; j >= h && (nums[j] < nums[j - h]); j -= h) {
//                    nums[j] ^= nums[j - h];
//                    nums[j - h] ^= nums[j];
//                    nums[j] ^= nums[j - h];
//                }
//            }
//            h /= 3;
//        }
//    }

    /**
     * 将数据分为三部分，尽量让012分布在最前面、中间、最后面
     * 所以需要三分切入，设置 zero 代表 0 与 1 的分界，two 代表1与2的分界
     * 再设置一个 i 用来遍历全部的数组，若 nums[i] == 1，则直接 i++
     * 若 nums[i] == 2，则需要把这个数放到后面那一坨 2 里面去，为此 two 应先 --，为存储nums[i]让出空间，然后交换位置
     * 若 nums[i] == 0，则需要把这个数放到前面那一坨 1 里面去，上面交换完位置后的数据可能是012中的任意一个，判断它若是0的话则
     *     应先让 zero++，为 num[i] 的插入腾出空间，再交换，因为此时的交换一定是1和0的交换，所以 i 也要 ++
     * @param nums
     */
    public static void sortColors3(int[] nums) {
        int zero = -1;
        int two = nums.length;
        for (int i = 0; i < two; ) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 2) {
                swap(nums, --two, i);
            } else {
                zero++;
                swap(nums, zero, i++);
            }
        }
    }

    public static void swap(int[] nums, int x, int y) {
        nums[x] ^= nums[y];
        nums[y] ^= nums[x];
        nums[x] ^= nums[y];
    }

    public static void main(String[] args) {
        int[] a = {2, 0, 2, 1, 1, 0};
        sortColors3(a);
        System.out.println(Arrays.toString(a));
    }
}

